Thời kỳ Công tước John còn sống, ông chủ trương dùng hôn nhân đối với các con của ông để củng cố thế lực khắp Châu Âu. Đầu tiên, William đã bị sắp đặt hôn nhân với Nữ vương Jeanne III của Navarra, nhưng họ đã huỷ hôn 4 năm sau đó. Ngay lập tức, William được dàn xếp hôn nhân với Maria của Áo - con gái của em trai Hoàng đế Karl là Đại vương công Ferdinand. Năm 1526, Công tước John gả chị cả của Anne là Sibylle cho Johann Friedrich I, Tuyển hầu xứ Sachsen, lãnh đạo Liên minh Schmalkaldic. Vào năm 11 tuổi (1527), Anne được hứa gả cho François de Lorraine, con trai của Antoine, Công tước xứ Lorraine, khi đó François chỉ mới 10 tuổi[7]. Việc hôn nhân này sau đó bị bác bỏ và tuyên bố hủy vào năm 1535, nhưng giấy cấp hủy không bao giờ có. Điều này dẫn đến vấn đề về sau của Anne khi cưới Henry VIII.

Vì việc tranh chấp Guelders với Hoàng đế Karl V của Thánh chế La Mã, đã khiến Công tước William được nhìn nhận là một đồng minh có thể lôi kéo của Vua Henry VIII nước Anh, và việc sắp xếp gặp gỡ giữa Henry VIII và Anne được dàn xếp bởi Thomas Cromwell. Họa sĩ Hans Holbein con đã được lệnh đến Düren để vẽ chân dung Anne, cùng người em gái là Amalia của Cleves - một người cũng được xem là ứng cử viên tốt cho vợ của Vua Henry. Sự điều đình với Cleves kết thúc vào tháng 3 năm 1539, đến ngày 4 tháng 10 cùng năm, Thomas Cromwell ký kết một điều ước hôn nhân với Cleves.

Khi đó từ năm 1538, theo đề nghị của Thomas Cromwell, Henry VIII cần phải cưới một người vợ mới không chỉ để giải quyết vấn đề chính trị, mà để nhà Vua có thể có thêm nhiều người thừa kế[8][9]. Một lý do khiến Henry VIII cần chọn vợ mới cũng là để mở rộng quan hệ quốc tế với Châu Âu lục địa, mảng đối ngoại đã bị phá hủy nghiêm trọng từ khi ông quyết định cưới Anne Boleyn. Sau cái chết của Jane Seymour, đây là lần đầu tiên Henry VIII có trạng thái "Góa vợ" một cách tự nhiên, không cưỡng ép hủy hôn hay xử tử người vợ, do đó càng cho ông có lý do tìm kiếm vợ mới, đặc biệt là cần phải xuất thân nước ngoài. Về mặt khác, sau khi Jane Seymour qua đời thì hơn 200 triều thần đã bị sa thải vì không còn Vương hậu duy trì nữa, một Thị tùng phục vụ trong triều là Anne Basset than thở:「"Cầu xin Chúa hãy nhanh ban cho Đức vua một người vợ mới"」. Có thể thấy xét chủ quan cá nhân lẫn khách quan chính trị, Henry VIII rất cần thiết có một Vương hậu[10]. Vào năm 1539, Hoàng đế Karl V của Thánh chế La Mã cùng François I của Pháp đã ký một hiệp ước liên minh, cũng như chủ trương trừng phạt Henry VIII của Giáo hoàng Paul III đã đẩy nước Anh vào thế cô lập. Không muốn chịu sự chống đối từ hai thế lực Công giáo mạnh mẽ này cùng một lúc (Hoàng đế cùng Giáo hoàng là một phe - và Pháp là một phe), Quốc vương Henry VIII quyết định phải liên hôn với một quốc gia cũng chống đối Công giáo, và gia tộc được cân nhắc suy xét nhất chính là nhà La Marck xứ Cleves[11].

Ban đầu, người được suy xét là Christina của Đan Mạch, một người cháu gọi Hoàng đế Karl V bằng cậu và là góa phụ của Francis II, Công tước Milan. Tuy nhiên Christina đã nhanh chóng từ chối, trong khi tin tức Hoàng đế Karl V ký hiệp ước cùng Pháp truyền đến, Henry VIII cuối cùng chọn được Anne của xứ Cleves - chị của Công tước William[12].

Theo nhãn quan tiêu chuẩn của bản thân Henry VIII, người là vợ của ông phải là một người có giáo dục cao và khả năng giao tiếp tốt, như Catherine xứ Aragon cùng Anne Boleyn, hay thậm chí là Jane Seymour, đều đạt được những giá trị này. Tuy nhiên, Anne xứ Cleves khi ấy lại thiếu những khía cạnh này vì bà không được giáo dục tỉ mỉ, khác hẳn chị cả Sibylle. Bà chủ yếu thành thạo việc nhà như may vá, hoặc các loại hình giải trí điển hình như chơi bài, chơi cờ. Bà cũng có thể đọc và viết, tuy nhiên chỉ là tiếng Đức[13], điều này đã khiến Anne tạo ấn tượng không tốt khi lần đầu gặp nhà Vua[14]. Những điều này lại không làm bận tâm triều đình Cleves, dù mẹ của Anne là Bà Công tước đã có ý phản đối cuộc hôn nhân này và quyến luyến vào ngày Anne rời khỏi Cleves. Bản thân nhà Vua Henry VIII có vẻ không để tâm chuyện này lên hàng đầu, khi ông rất hả hê vì biết cuộc hôn nhân sẽ chọc tức Hoàng đế Karl V của Thánh chế La Mã[15].

Về mặt khác, Anne được nhận xét là dịu dàng, đoan chính và ngoan ngoãn, rất hợp với yêu cầu cơ bản của Henry VIII về đức tính của một người vợ. Dù rằng Henry VIII có yêu cầu về giáo dục và ngoại giao, song như những gì ông cảnh cáo Jane Seymour, một người vợ chỉ nên vâng lời chồng và không được can thiệp chính trị, vì vậy sự thiếu hụt giáo dục của Anne phần nào lại rất an toàn với vai trò một Vương hậu không có khả năng can thiệp chính trị của nhà Vua. Sứ giả người Pháp là Charles de Marillac mô tả Anne có vóc dáng cao và mảnh mai, tuy có nhan sắc không quá nổi bật, nhưng bà rất đoan trang huệ hạ[16]. Theo mô tả, Anne có mái tóc màu sáng và được tả lại có khuôn mặt khả ái. Cũng theo nhà biên niên sử gia Edward Hall, Anne xứ Cleves được nhìn nhận là:「"... (Bà ấy) có mái tóc thẳng, dài và màu vàng... Khi đến đây, đức bà mặc một bộ trang phục điển hình kiểu Anh, với một mũ trùm 'Hood' theo phong cách Pháp, càng tôn thêm vẻ đẹp của bà. Những kẻ dưới đều tranh nhau chiêm ngưỡng bà"」[17]. Nhìn chung, ấn tượng của người Anh về bà khá là uy nghiêm. Họa sĩ Holbein vẽ bà có cặp mắt mí khá dày, vầng trán cao vút và có cái cằm nhọn.